1. Field
The present invention relates to path search techniques and, more particularly, to systems and methods to aid routing around obstacles such as for integrated circuit (e.g., VLSI) routing.
2. Description of the Related Art
There are many important practical applications for path searching. The classic, student's example is the traveling salesman searching for an efficient path to visit a list of locations. Some search methods are useful to plan the movement of a robot across a room around obstacles such as furniture or the movement of a robot arm through space around obstacles. One practical and currently very important engineering application of path searching is found in the semiconductor and electronics arts. Path searching and routing techniques are typically employed for layout of conductive traces. Other practical applications are well known.
The classical path searching problem and current techniques can be understood in the context of searching for a shortest path from a source point or location to a target point or location through clear space of a routing region (two-dimensional or otherwise) around various obstacles in the routing region. More specifically, assume that inside a rectangular routing region there are several rectilinear obstacles. The space not occupied by the obstacles may be called clear space. For any given two points inside the clear space, the minimum cost path search problem is to find the path with the minimum cost (e.g., the shortest path or by some other measure) inside the clear space that connects them.
Computational efficiency of path search and routing techniques is important, particularly for complex routing problems such as those presented by modern semiconductor technology and applications such as VLSI routing. Existing approaches to solving this problem typically suffer from at least one, and sometimes all of the following disadvantages: (i) complexity, (ii) overlong computational time, (iii) failure to achieve an optimal path when multiple paths exist, (iv) failure to find a path when one exists. The semiconductor routing industry, for example, is constantly looking to improve techniques for solving this problem to mitigate or eliminate the above disadvantages.